//优先级队列，底层是用到了堆来模拟实现优先级的
//里面的写点就是堆，然后就是这种设计模式

#include<iostream>
#include<vector>
using namespace std;

namespace cxy{
	template<class T>
	struct less{
		bool operator()(const T& x1,const T& x2){
			return x1 < x2;
		}
	};
	template<class T>
	struct greater{
		bool operator()(const T& x1, const T& x2){
			return x1 > x2;
		}
	};
	template<class T,class Container=vector<T>,class Compare=cxy::less<T>>
	class priority_queue{
	public:
		typedef typename vector<T>::iterator iterator;
		//priority_queue是适配器适配的，其中可以有vector、string、queue、stack等
		//但是queue和stack不支持迭代器，所以库中没有实现迭代器。
		//默认是用vector适配
		//queue和stack也是用适配器来适配的，模式deque适配的
		iterator begin(){
			return _con.begin();
		}
		iterator end(){
			return _con.end();
		}

		void UpAdjdust(size_t child){
			size_t parent = (child - 1) / 2;
			while (child>0){
				//向上调整，在新插入节点之前，该推结构没有破坏。
				//当插入节点的时候，只需要调整该节点带根这一条路径就行
				if (Compare()(_con[child], _con[parent])){
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else{
					break;
				}
			}
		}
		void UnderAdjdust(size_t parent){
			size_t child = 2 * parent + 1;
			while (child<_con.size()){
				if (child + 1 < _con.size() && Compare()(_con[child + 1], _con[child])){
					child++;
				}
				if (Compare()(_con[child], _con[parent])){
					swap(_con[parent], _con[child]);
					parent = child;
					child = 2 * parent + 1;
				}
				else{
					break;
				}
			}
		}
		void push(const T& t){
			_con.push_back(t);
			//调整堆
			UpAdjdust(_con.size()-1);
		}
		void pop(){
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			UnderAdjdust(0);
		}

		T& top(){
			return _con[0];
		}	
		size_t size(){
			return _con.size();
		}
		bool empty(){
			return _con.empty();
		}
	private:
		Container _con;
	};

	void text1(){
		priority_queue<int, vector<int>, greater<int>> q;
		q.push(1);
		q.push(2);
		q.push(3);
		q.push(6);
		q.push(5);
		q.push(4);
		
		priority_queue<int, vector<int>, greater<int>>::iterator it = q.begin();
		while (it != q.end()){
			cout << *it << endl;
			it++;
		}
		cout << "断点" << endl;
	}
}